# include <bits/stdc++.h>
using namespace std;

char word[10023], text[1000023];
int ne[10023];
inline void get_ne(char *st) {
	int n = strlen(st);
	int i = 0, j = -1;
	ne[0] = -1;
	while(i < n) {
		while(~j && st[i] != st[j]) j = ne[j];
		ne[++i] = ++j;
	}
}
inline int KMP(char *str, char *st) {
	int i = 0, j = 0;
	int ans = 0, n = strlen(str), m = strlen(st);
	while(i < n) {
		while(~j && str[i] != st[j]) j = ne[j];
		i++, j++;
		if(j == m) ans++;
	}
	return ans;
}
int main() {
	freopen("oulipo.in", "r", stdin);
	freopen("oulipo.out", "w", stdout);
	int t = 0;
	cin >> t;
	while(t--) {
		scanf("%s%s", word, text);
		get_ne(word);
		printf("%d\n", KMP(text, word));
	}

}
